class Solution {
    public int slidingPuzzle(int[][] board) {
        distance = new HashMap<>();
        int origin = zip(board);
        distance.put(origin, 0);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(origin);
        while (!queue.isEmpty()) {
            int topVal = queue.poll();
            if (topVal == 123450) {
                return distance.get(topVal);
            }
            int[][] top = unzip(topVal);
            int distanceTop = distance.get(topVal);
            Pair<Integer, Integer> zeroPosition = findZeroPosition(top);
            int x = zeroPosition.getKey();
            int y = zeroPosition.getValue();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx <= 1 && ny >= 0 && ny <= 2) {
                    top[x][y] = top[nx][ny];
                    top[nx][ny] = 0;
                    int nextVal = zip(top);
                    if (!distance.containsKey(nextVal) || distanceTop + 1 < distance.get(nextVal)) {
                        queue.offer(nextVal);
                        distance.put(nextVal, distanceTop + 1);
                    }
                    top[nx][ny] = top[x][y];
                    top[x][y] = 0;
                }
            }
        }
        return -1;
    }
    private Pair<Integer, Integer> findZeroPosition(int[][] board) {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 0) {
                    return new Pair<>(i, j);
                }
            }
        }
        return new Pair<>(-1, -1);
    }
    private int zip(int[][] board) {
        int res = 0;
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                res = res * 10 + board[i][j];
            }
        }
        return res;
    }
    private int[][] unzip(int value) {
        int[][] board = new int[2][3];
        for (int i = 1; i >= 0; i--) {
            for (int j = 2; j >= 0; j--) {
                board[i][j] = value % 10;
                value /= 10;
            }
        }
        return board;
    }
    private Map<Integer, Integer> distance;
    private int[] dx = new int[]{0, 1, 0, -1};
    private int[] dy = new int[]{1, 0, -1, 0};
}
